package thired.algorithm;

import com.sun.deploy.util.StringUtils;

import javax.xml.bind.SchemaOutputResolver;
import java.util.Locale;

public class IsManacher {
    public static boolean manacher(String input){
        if (input == null || input.length() == 0) {
            return true;
        }
        String s = input.replaceAll("[^a-zA-Z0-9]","").toLowerCase(Locale.ROOT);
        char[] str = manacherString(s);
        int C = -1;
        int R = -1;
        int[] pArr = new int[str.length];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] >= 0){
                if(str[i + pArr[i]] == str[i - pArr[i]]){
                    pArr[i]++;
                }else{
                    break;
                }
            }
            if(i + pArr[i] > R){
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        return max - 1 == s.length();
    }

    private static char[] manacherString(String s) {
        char[] s1 = s.toCharArray();
        char[] res = new char[2 * s.length() + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : s1[index++];
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(manacher("A ,,,,, abbaA"));
    }
}
